package leetcode.editor.week.week308;

import java.util.LinkedList;
import java.util.Queue;

// 2391. 收集垃圾的最少总时间
// https://leetcode.cn/problems/minimum-amount-of-time-to-collect-garbage/
public class Solution2392 {
    public static void main(String[] args) {
        Solution2392 solution2392 = new Solution2392();
        solution2392.buildMatrix(3, new int[][]{{1, 2}, {3, 2}}, new int[][]{{2, 1}, {3, 2}});
    }

    // https://leetcode.cn/problems/build-a-matrix-with-conditions/solution/by-tong-zhu-4uv6/
    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        // 记录了数字存储在哪一行
        int[] row = findOrder(k, rowConditions);
        int[] col = findOrder(k, colConditions);
        // 判断是否有环
        if (row[0] == -1 || col[0] == -1) return new int[][]{};
        int[][] res = new int[k][k];
        for (int i = 1; i <= k; i++) {
            res[row[i]][col[i]] = i;
        }
        return res;
    }

    // BFS拓扑排序
    public int[] findOrder(int k, int[][] graph) {
        Queue<Integer> queue = new LinkedList<>();
        int[] indegree = new int[k + 1];
        LinkedList<Integer>[] graphList = new LinkedList[k + 1];
        for (int i = 1; i <= k; i++) {
            graphList[i] = new LinkedList<>();
        }

        for (int[] v : graph) {
            int from = v[0], to = v[1];
            graphList[from].add(to);
            indegree[to]++;
        }

        // 入度为0的加入队列
        for (int i = 1; i <= k; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 记录拓扑排序结果
        int[] res = new int[k + 1];
        int count = 0;  // 表示行数
        while (!queue.isEmpty()) {
            Integer cur = queue.poll();
            // 存储的是哪个数字放在哪一行，而不是哪行存储哪个数字
            res[cur] = count;
            count++;
            for (int next : graphList[cur]) {
                indegree[next]--;
                if (indegree[next] == 0) queue.offer(next);
            }
        }

        if (count != k) {
            // 标记一下有环，用第一位即可，不用申请变量
            res[0] = -1;
        }

        return res;
    }

}
